# 二叉树的右视图
# 同理二叉树的左视图也是一样的



class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# 层序构建二叉树
def array_to_binary_tree(arr:list) -> TreeNode:
    if not arr and arr[0] is None:
        return None
    
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    # print(len(arr))
    while queue and i < len(arr):
        node = queue.pop(0)

        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
            
        i += 1
        
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    

    return root

class solution:

    def rightSideView(self, root: TreeNode) -> list[int]:
        ans = []

        def dfs(node:TreeNode, depth: int) -> None:
            if not node:
                return
            if depth == len(ans):
                ans.append(node.val)
            
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return ans
    

if __name__ == "__main__":

    # arr = [1, 2, 3, None, 5, None, 4]
    arr = [1, 2, 3, 4, None, None, None, 5]
    root = array_to_binary_tree(arr)
    
    sol = solution()

    ans = sol.rightSideView(root)

    print(ans)



